problem

輸入為一陣列，回傳陣列是否為單調陣列 (monotonic array)。

單調陣列有兩種情況：陣列為單調遞增 (非遞減)，或單調遞減 (非遞增)。單看中文很難懂，直接看比較。

嚴格遞增：每一個元素都大於前一個元素。
單調遞增：每一個元素都大於或等於前一個元素。

嚴格遞減：每一個元素都小於前一個元素。
單調遞減：每一個元素都小於或等於前一個元素。

也就是說單調陣列在遞增或遞減的過程中可以接受連續相同的元素。另外，空陣列或只有一個元素的陣列也算是單調陣列。

sample input:
array = [-1, -5, -10, -1100, -1100, -1102, -9001]

sample output:
true

這個題目可能麻煩的點在於，有兩種情況要確認，另外還需要考慮可能有相同的元素。解析中提到，目測應該會利用迴圈，可以找到線性時間解．而且應該不需要額外的空間。所以這題追求的可能不是時間更優化的解法，而是找到解法並寫出清楚的程式。

solution 01

可以先假設題目問的是嚴格遞增或嚴格遞減的清況，也就是每個元素一定要比前一個大或小。可能的做法是先判斷出陣列的走向，也就是檢查第一個和第二個元素，如果是遞增，那就檢查後面所有元素是否都符合遞增的關係。

但這個作法放在單調陣列可能不太好用，例如 [1, 1, 1, 2] 有重複元素，無法只以頭兩個數字判斷走向。所以作法可能要改變為，兩兩比較陣列中的所有數字，紀錄走向，直到首次出現非持平的走向，則檢查後續所有數字是否符合。

n 為陣列長度
time: O(n)
space: O(1)

function isMonotonic(array) {
  if (array.length <= 2) {
    return true;
  }
  // 利用差值為正數或負數來表示遞增或遞減
  let direction = array[1] - array[0];
  for (let i = 2; i < array.length; i++) {
    // 如果目前走向是持平 更新走向
    if (direction === 0) {
      direction = array[i] - array[i - 1];
      continue
    }
    // 否則檢查是否不符合走向
    if (breaksDirection(direction, array[i - 1], array[i])) {
      return false;
    }
  }
  return true;
}

function breaksDirection(direction, previousInt, currentInt) {
  const difference = currentInt - previousInt;
  if (direction > 0) return difference < 0;
  return difference > 0;
}

關於第 14 行檢查是否破壞走向的部分，主要就是用當前兩數的差值和 direction 是否一個大於零且另一個小於零來做判斷。範例程式碼的做法是另外寫一個非常語意化的函式，可以參考。

solution 02

假設題目只問陣列是否為單調遞增，也就是只考慮其中一種情況，這樣的檢查會變很單純，只需要看每個數字是否都大於等於前一個數字即可。

所以第二種解法的想法是，如果只考慮 '是否為單調遞增' 或 '是否為單調遞減' 很簡單，那可不可以在迴圈過每個數字時，結合這兩種簡單的檢查？
例如陣列 [-1, -5, -10, -1100, -1100, -1102, -9001]

1. 有兩種可能的情況：(1) 單調遞增，(2) 單調遞減。
2. 比較頭兩個數字，-1, -5，
   是情況 (1) 嗎？ no → 情況 (1) 為 false
   是情況 (2) 嗎？ yes
3. 重複以步驟 2 檢查陣列中的每兩個相鄰數字，最後回傳 (1)、(2) 中仍然為 true 的情況，都沒有則回傳 false。

這種解法的時間空間複雜度跟前一解法一樣，只是更簡單，比較不容易出錯。寫前一個解法可能會覺得邏輯無誤，應該沒什麼問題，但看到這個解就覺得...嗯我考試要寫這種...

function isMonotonic(array) {
  let isNonDecreasing = true;
  let isNonIncreasing = true;
  for (let i = 1; i < array.length; i++) {
    if (array[i] < array[i - 1]) isNonDecreasing = false;
    if (array[i] > array[i - 1]) isNonIncreasing = false;
  }
  return isNonDecreasing || isNonIncreasing;
}